package pers.qianyu.month_202101.date_20210131;

import org.junit.*;

import java.util.*;

/**
 * 第 226 场周赛 第 2 题
 * 5665. 从相邻元素对还原数组
 * https://leetcode-cn.com/problems/restore-the-array-from-adjacent-pairs/
 *
 * @author mizzle rain
 * @date 2021-01-31 14:50
 */
public class RestoreArray2 {
    private final Map<Integer, List<Integer>> map = new HashMap<>();
    private List<Integer> path = new ArrayList<>();

    // 邻接表
    public int[] restoreArray(int[][] pairs) {
        int len = pairs.length;
        // 构建领接表，并且统计每个数字出现的次数
        HashMap<Integer, Integer> countMap = new HashMap<>();
        for (int[] pair : pairs) {
            List<Integer> list = map.getOrDefault(pair[0], new ArrayList<>());
            list.add(pair[1]);
            map.put(pair[0], list);
            list = map.getOrDefault(pair[1], new ArrayList<>());
            list.add(pair[0]);
            map.put(pair[1], list);

            countMap.put(pair[0], countMap.getOrDefault(pair[0], 0) + 1);
            countMap.put(pair[1], countMap.getOrDefault(pair[1], 0) + 1);
        }

        // 找到一个出现次数为 1 的结点，作为头结点开始遍历
        int root = -1;
        for (int k : countMap.keySet()) {
            int v = countMap.get(k);
            if (v == 1) {
                root = k;
                break;
            }
        }
        // 深搜
        dfs(root, -1);

        int[] res = new int[path.size()];
        for (int i = 0; i < path.size(); i++) res[i] = path.get(i);
        return res;
    }

    private void dfs(int root, int pre) {
        path.add(root);
        for (int x : map.get(root)) {
            if (x != pre) {
                dfs(x, root);
            }
        }
    }

    @Test
    public void test1() {
        int[] result = new RestoreArray2().restoreArray(new int[][]{{2, 1}, {3, 4}, {3, 2}});
        System.out.println("result = " + Arrays.toString(result));
    }

    @Test
    public void test2() {
        int[] result = new RestoreArray2().restoreArray(new int[][]{{4, -2}, {1, 4}, {-3, 1}});
        System.out.println("result = " + Arrays.toString(result));
    }

    @Test
    public void test3() {
        int[] result = new RestoreArray2().restoreArray(new int[][]{{100000, -100000}});
        System.out.println("result = " + Arrays.toString(result));
    }
}
